1. Field of the Invention
The invention disclosed herein is related to the determination of interconnections or paths between terminals of interoperable components. More specifically, the invention is related to resolving layout congestion in a routing or path-finding phase during which spatial restrictions otherwise imposed are temporarily suspended. Such methodology is applicable in such fields as automatic circuit path routing, or autorouting, of printed and integrated circuits.
2. Description of the Prior Art
Electrical circuit autorouters have been in use for decades, the majority of which are geometry-based, in which routing objects are represented by obstacles such as pads, pre-existing wire segments, keep-out regions, etc. Typically, the available routing space is represented by a plurality of polygons, such as rectangles or, occasionally, octagons. These polygons are located at explicit coordinates and the geometric autorouter's path finding routines explore the geometric data associated with these and other objects to find new paths. The exploration may proceed by traversing grids or other shape-based spatial divisions, but always in accordance with the geometry defining the routing space.
Once the potential paths, or routes, have been obtained by the path finding procedures, path resolving procedures correct defects in the routing so that design-rule-correct (DRC) wire segments that form the physical electrical connections will properly fit in the space provided. For example, in certain instances, the path finding procedures may select a potential route between items already placed in the given circuit arrangement where the placement of wire segments on that route would violate congestion constraints. When this occurs, the path resolving procedures may attempt to move an existing item so as to accommodate the desired configuration. The process of moving items to make room for other items is referred to herein as a “shove”. Shove procedures in geometric autorouters, where they are implemented, require concurrent manipulation of both terminal pads and wire segments by applying spatial operations directly on the associated geometric information. Unfortunately, moving potentially complex shapes in a geometrically defined routing space can be computationally intensive and therefore, extremely slow.
A small number of autorouters are topology-based, where the routing space is divided into, for example, a plurality of triangles and the routing objects are represented in a topological graph residing in the divided routing space. Although the routing objects are known to have geometric locations and physical dimensions, these attributes do not burden the computations during portions of the topological routing phase. The path finding processes explore the topological routing space using “betweenness” rules, as opposed to geometric “fitting” rules. For example, the path finding procedure of a topological router may consider a particular path as being between two particular topological features, but the exact location in the coordinates of the geometric routing space where the path will ultimately pass between those features might not be exactly known at the time of topological routing. The paths found by the topological router may then be used by a geometric autorouter as base traces on which to create the DRC wire segments.
A topology-based autorouter has the advantage that a topological graph is very fluid. Exact locations in the topological routing space are not essential to the topological routing process, so objects can be moved about freely to accommodate new paths. Overloads can be easily tolerated during early routing passes.
By comparison, the path resolution measures of the geometry-based autorouter must be run immediately after the path finding procedures to avoid corruption of the geometric solution. The ability of a topological autorouter to be fluid, allowing overloads and crossed wires, may be its single most important advantage over geometry-based autorouters. But, to take full advantage of this fluidity, additional processes to resolve overloads must be implemented that operate on the topological graph. Overloads that are not eliminated immediately after the path finding procedures have completed execution are more difficult to resolve in later routing stages. Moreover, the path resolution procedures of a geometric router might not be able to create a DRC geometric solution based on a candidate topological solution in which overloads still exist. Therefore, some overload resolution mechanism is needed in all topology-based autorouters if high completion rates are to be achieved.
Currently, topological autorouting is limited to single-layer applications, where there are no vias (conductive elements electrically coupling different layers). Since vias are not used in single-layer applications, there are few, if any, opportunities to execute shoves to resolve overloads. Vias may be easily relocated by shove operations since they are not spatially tied to any other pad on a layer. Shoving most other pads on a layer is usually impracticable, as the spacing of pads is often fixed by the spacing of the associated component, such as by the package terminals of an integrated circuit. Previously, the only technique available to remove overloads in single-layer applications was to effect a reroute of the circuit with an increased penalty imposed for subsequent routing the path in the overloaded region. The technique works, however, rerouting involves inherently slow path finding routines. Generally, for multi-layer routing, high completion rates cannot be achieved efficiently without applying shoving operations to vias.
In view of the limitations of the prior art, the need is felt for a topological autorouter that is capable of resolving overloads during a topological routing stage of operation, where such routing is fluid. Such an autorouter should permit the shoving of vias, where available, and should include other overload resolving procedures should the shove operation fail or be otherwise impracticable. Only after the resolution of overloads in the topological routing stage should the geometric arrangement of the circuit be established.